<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>One-pass algorithm</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/One-pass_algorithm"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-One-pass_algorithm rootpage-One-pass_algorithm skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">One-pass algorithm</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<style data-mw-deduplicate="TemplateStyles:r1305433154">
/* start https://en.wikipedia.org/ */
.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}
/* end https://en.wikipedia.org/ */
</style>
<p>In computing, a <b>one-pass algorithm</b> or <b>single-pass algorithm</b> is a <a href="Streaming_algorithm" title="Streaming algorithm">streaming algorithm</a> which reads its input exactly once.<sup id="cite_ref-frankfurt_1-0" class="reference"><a href="#cite_note-frankfurt-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It does so by processing items in order, without unbounded <a href="Buffer_(computer_science)" class="mw-redirect" title="Buffer (computer science)">buffering</a>; it reads a block into an <a href="Input_buffer" class="mw-redirect" title="Input buffer">input buffer</a>, processes it, and moves the result into an output buffer for each step in the process.<sup id="cite_ref-sjsu_2-0" class="reference"><a href="#cite_note-sjsu-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> A one-pass algorithm generally requires <i>O</i>(<i>n</i>) (see <a href="Big_O_Notation" class="mw-redirect" title="Big O Notation">'big O' notation</a>) time and less than <i>O</i>(<i>n</i>) storage (typically <i>O</i>(1)), where <i>n</i> is the size of the input.<sup id="cite_ref-eds_3-0" class="reference"><a href="#cite_note-eds-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> An example of a one-pass algorithm is the Sondik <a href="Partially_observable_Markov_decision_process" title="Partially observable Markov decision process">partially observable Markov decision process</a>.<sup id="cite_ref-pomdp_4-0" class="reference"><a href="#cite_note-pomdp-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Example_problems_solvable_by_one-pass_algorithms">Example problems solvable by one-pass algorithms</h2></div>
<p>Given any list as an input:
</p>
<ul><li>Count the number of elements.</li></ul>
<p>Given a list of numbers:
</p>
<ul><li>Find the <i>k</i> largest or smallest elements, <i>k</i> given in advance.</li>
<li>Find the <a href="Summation" title="Summation">sum</a>, <a href="Mean" title="Mean">mean</a>, <a href="Variance" title="Variance">variance</a> and <a href="Standard_deviation" title="Standard deviation">standard deviation</a> of the elements of the list. See also <a href="Algorithms_for_calculating_variance" title="Algorithms for calculating variance">Algorithms for calculating variance</a>.</li></ul>
<p>Given a list of symbols from an alphabet of <i>k</i> symbols, given in advance.
</p>
<ul><li>Count the number of times each symbol appears in the input.</li>
<li>Find the most or least frequent elements.</li>
<li>Sort the list according to some order on the symbols (possible since the and after number of symbols is limited).</li>
<li>Find the maximum gap between two appearances of a given symbol.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Example_problems_not_solvable_by_one-pass_algorithms">Example problems not solvable by one-pass algorithms</h2></div>
<p>Given any list as an input:
</p>
<ul><li>Find the <i>n</i>th element from the end (or report that the list has fewer than <i>n</i> elements).</li>
<li>Find the middle element of the list. However, this is solvable with two passes: Pass 1 counts the elements and pass 2 picks out the middle one.</li></ul>
<p>Given a list of numbers:
</p>
<ul><li>Find the <a href="Median" title="Median">median</a>.</li>
<li>Find the <a href="Mode_(statistics)" title="Mode (statistics)">modes</a> (This is not the same as finding the most frequent symbol from a limited alphabet).</li>
<li>Sort the list.</li>
<li>Count the number of items greater than or less than the <a href="Mean" title="Mean">mean</a>. However, this can be done in constant memory with two passes: Pass 1 finds the average and pass 2 does the counting.</li></ul>
<p>The two-pass algorithms above are still <a href="Streaming_algorithm" title="Streaming algorithm">streaming algorithms</a> but not one-pass algorithms.
</p>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-frankfurt-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-frankfurt_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFSchweikardt" class="citation web cs1">Schweikardt, Nicole. <a rel="nofollow" class="external text" href="http://www.tks.informatik.uni-frankfurt.de/schweika/downloads/EncycDBS_OnePassAlgos.pdf">"One-Pass Algorithm"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-07-01</span></span>.</cite></span>
</li>
<li id="cite_note-sjsu-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-sjsu_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFPollett2005" class="citation web cs1">Pollett, Chris (2005-03-14). <a rel="nofollow" class="external text" href="http://www.cs.sjsu.edu/faculty/pollett/157b.12.05s/Lec14032005.pdf">"One and Two Pass Algorithms"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-07-01</span></span>.</cite></span>
</li>
<li id="cite_note-eds-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-eds_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchweikardt2009" class="citation cs2">Schweikardt, Nicole (2009), <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-0-387-39940-9_253">"One-Pass Algorithm"</a></span>, in <a href="Ling_Liu_(computer_scientist)" title="Ling Liu (computer scientist)">LIU, LING</a>; ÖZSU, M. TAMER (eds.), <i>Encyclopedia of Database Systems</i>, Boston, MA: Springer US, pp. <span class="nowrap">1948–</span>1949, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-39940-9_253">10.1007/978-0-387-39940-9_253</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-39940-9</bdi><span class="reference-accessdate">, retrieved <span class="nowrap">2021-04-13</span></span></cite></span>
</li>
<li id="cite_note-pomdp-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-pomdp_4-0">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.pomdp.org/tutorial/sondik.html">"Sondik's One-Pass Algorithm"</a>. <i>www.pomdp.org</i>.</cite></span>
</li>
</ol></div>
<style data-mw-deduplicate="TemplateStyles:r1271159938">
/* start https://en.wikipedia.org/ */
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}
/* end https://en.wikipedia.org/ */
</style></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-06-30" href="https://en.wikipedia.org/wiki/?title=One-pass_algorithm&oldid=1298046753">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>